package com.mori.algorithm;

import java.util.Arrays;

/**
 * <p> 梳排序（Comb sort）是一种由Wlodzimierz Dobosiewicz于1980年所发明的不稳定排序算法，
 * 并由Stephen Lacey和Richard Box于1991年四月号的Byte杂志中推广。梳排序是改良自泡沫排序和快速排序，
 * 其要旨在于消除乌龟，亦即在数组尾部的小数值，这些数值是造成泡沫排序缓慢的主因。
 * 相对地，兔子，亦即在数组前端的大数值，不影响泡沫排序的性能。 </p>
 *
 * @author mori
 * @since 10/24/2019 2:03 PM
 */
public class CombSort {

    public static void main(String[] args) {
        int[] arr = {10, 1, 18, 30, 23, 12, 7, 5, 19, 17};
        System.out.println(Arrays.toString(arr));
        combSort(arr);
        System.out.println(Arrays.toString(arr));
    }


    private static void combSort(int[] arr) {
        int length = arr.length;
        int step = (int) (arr.length / 1.3);
        while (step >= 1) {
            for (int i = 0; i + step < length; i++) {
                if (arr[i] > arr[i + step]) {
                    arr[i] = arr[i + step] + (arr[i + step] = arr[i]) * 0;
                }
            }
            step /= 1.3;
        }
    }
}
